package tree.BinarySearchTree;

import tree.TreeNode;

/**
 * @ClassName DeleteBST
 * @Description TODO
 * @Author lenovo
 * @Date 2023-04-13 9:55
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class DeleteBST {
    /**

     *
     450. 删除二叉搜索树中的节点
     给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

     一般来说，删除节点可分为两个步骤：

     首先找到需要删除的节点；
     如果找到了，删除它。


     示例 1:



     输入：root = [5,3,6,2,4,null,7], key = 3
     输出：[5,4,6,2,null,null,7]
     解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
     一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
     另一个正确答案是 [5,2,6,null,4,null,7]。
                 6
     *     2
     *  1     4
     *
                 6
     *     2
     *  1     4
     *     3
     *
     *
                 6
     *     2
     *  1     3
     *           5
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root.val>key){
            root.left = deleteNode(root.left,key);
        }else if(root.val<key){
            root.right = deleteNode(root.right,key);
        }else{
            if(root.left==null)return root.right;
            if(root.right==null) return root.left;
            TreeNode tempNode = root.right;
            while(tempNode.left!=null){
                tempNode = tempNode.left;
            }
            root.val = tempNode.val;
            deleteNode(root.right,tempNode.val);
        }
        return root;
    }


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(6);
        treeNode.left = new TreeNode(2);
        treeNode.left.left = new TreeNode(1);
        treeNode.left.right = new TreeNode(4);
        treeNode.left.right.left = new TreeNode(3);
        DeleteBST deleteBST = new DeleteBST();
        System.out.println(deleteBST.deleteNode(treeNode, 2));
    }
}